A video file is made up of a series of frames. Each frame may be similar to a few frames preceding it and a few frames following it. Often, several frames in a video file depict the same object, but the position of the object moves from frame to frame. Thus, significant portions of multiple frames may be translations (i.e., shifted versions) of a particular frame, known as a reference frame. A reference frame may be a frame of the video file, or a combination of two or more frames of the video file. To reduce the amount of memory needed to store a video file during video coding and compression, motion vectors representing translations of reference frames may be stored, rather than all information from every frame being stored. Because frames in a video file are not all perfect translations of a reference frame, each stored motion vector may have an associated error, which may also be stored.
Motion estimation is a well-known aspect of video coding and compression. Motion estimation is the process of selecting the best motion vectors for representing the spatial displacement between reference frames and other frames. A frame may be divided into multiple blocks of pixels, and an optimum motion vector may be determined for each block. Each block has a multitude of possible motion vectors (e.g., vectors that shift the block vertically, horizontally, or diagonally). A vector with the lowest cost, in terms of how much error results from using the vector, may be an optimum motion vector.
Various cost functions may be used to determine an optimum motion vector for each block. Common cost functions include sum of absolute difference (SAD) and sum of absolute transformed difference (SAID). The SAD cost function involves relatively simple calculations, but does not yield accurate results for non-integer vectors. The SAID cost function has better accuracy for sub-pixel vectors, but is expensive (e.g., in terms of processing power, latency time) because large 2-dimensional transforms must be calculated.